/*
 * Huffman coding
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>
#include <stdint.h>

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif

#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

struct huff_node {
	int weight;
	char ch;
	bool is_leaf;

	struct huff_node *left; /* 0 */
	struct huff_node *right; /* 1 */
	struct huff_node *parent;
};

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}

void
s_free(void *ptr)
{
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): freeing %p\n", __func__, ptr);
#endif
	free(ptr);
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n >= 1);
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		#ifdef QUEUE_DEBUG
		fprintf(stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max);
		#endif /* QUEUE_DEBUG */
		return -1;
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	#ifdef QUEUE_DEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif /* QUEUE_DEBUG */

	return 0;
}

extern int
queue__peek(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	if (q->n > 0) {
		memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	} else {
		memset(buf, 0, q->_data_size);
	}

	return 0;
}

/*
 * TODO: when 'buf' is NULL disregard the first element
 */
extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif /* QUEUE_DEBUG */

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	s_free(q->data);
	q->data = NULL;
	s_free(q);

	return 0;
}
/* }}} */

/* {{{ misc */
extern char *
bytes_to_str(const void *ptr, const size_t size)
{
	char *str;
	const unsigned char *byte = ptr;
	int offset;

	/* each byte is represented as "??" and a
	 * whitespace character in between */
	str = s_malloc((2 + 1) * size + 1);
	for (offset = 0; offset < size; offset++) {
		sprintf(str + offset * 3, "%02hhX ", byte[offset]);
	}
	str[size * 3 - 1] = '\0';

	return str;
}

char *
bits_to_str(const unsigned char *data, register int nbits, register int i)
{
	char *str;

	S_assert(i >= 0);
	while (i >= 8) {
		i -= 8;
		nbits -= 8;
		data++;
	}
	str = s_malloc(nbits + 1);
	while (i < nbits) {
		*str = '0' + ((*data >> (CHAR_BIT - 1 - (i & 07))) & 1);
		i++;
		str++;

		if ((i & 07) == 07)
			data++;
	}
	*str = '\0';

	return str;
}

char *
int_to_bitstr(const int x)
{
	char *str;
	register int i = 0;
#define TYPE_BIT	(CHAR_BIT * sizeof x)

	str = s_malloc(TYPE_BIT + 1UL);
	for (i = 0; i < (TYPE_BIT); i++)
		str[i] = '0' + ((x >> (TYPE_BIT - i - 1)) & 1);
	str[TYPE_BIT] = '\0';

	return str;
#undef TYPE_BIT
}
/* }}} */

int
cmp_huff_nodes(const void *p1, const void *p2)
{
	const struct huff_node *a = * (const struct huff_node **) p1,
	                       *b = * (const struct huff_node **) p2;

	if (a->weight < b->weight)
		return -1;
	if (a->weight > b->weight)
		return 1;
	if (a->ch != b->ch)
		return (int) a->ch - b->ch;
	S_assert('a' == 'b');
	return 0; /* unreach */
}

unsigned int *
count_frequencies(const unsigned char *text, const int length)
{
	unsigned int *frq;
	register int i = 0;

	frq = s_calloc(1 << CHAR_BIT, sizeof frq[0]);

	for (i = 0; i < length; i++)
		frq[text[i]]++;

	return frq;
}

struct huff_node *
huffman_build_tree(unsigned int *frequencies)
{
	struct queue *q1, *q2; /* q1 - nodes, q2 - parents. could also use priority queue */
	struct huff_node *nd, *root;
	struct huff_node *tmp[256]; /* XXX: assuming CHAR_BIT is 8 */
	register int i = 0, j = 0;
	int n;
	struct huff_node *min[2];

	while (i < (1 << CHAR_BIT)) {
		if (frequencies[i] == 0) {
			i++;
			continue;
		}
		tmp[j] = s_malloc(sizeof (struct huff_node));
		tmp[j]->weight = frequencies[i];
		tmp[j]->ch = i;
		tmp[j]->is_leaf = true;
		tmp[j]->parent = tmp[j]->left = tmp[j]->right = NULL;

		i++;
		j++;
	}
	n = j;

	/*mergesort(tmp, n, sizeof tmp[0], cmp_huff_nodes);*/
	qsort(tmp, n, sizeof tmp[0], cmp_huff_nodes);

	q1 = queue__new(n, sizeof tmp[0]);
	for (i = 0; i < n; i++)
		queue__push(q1, &tmp[i]);
	q2 = queue__new(n - 1, sizeof tmp[0]);

	/*
	 * XXX
	 * Here's where the magic happens
	 */
	while (q1->n + q2->n > 1) {
		queue__peek(q1, &min[0]);
		queue__peek(q2, &nd);
		if (min[0] == NULL || nd != NULL &&
				cmp_huff_nodes(&min[0], &nd) > 0) {
			/* q1[0] > q2[0] -> choose q2 */
			queue__pop(q2, &min[0]);
		} else {
			queue__pop(q1, &min[0]);
		}

		queue__peek(q1, &min[1]);
		queue__peek(q2, &nd);
		if (min[1] == NULL || nd != NULL &&
				cmp_huff_nodes(&min[1], &nd) > 0) {
			/* q1[0] > q2[0] -> choose q2 */
			queue__pop(q2, &min[1]);
		} else {
			queue__pop(q1, &min[1]);
		}

		/*
		 * so, now we have links to two nodes in min[]
		 * here we make a parent for them
		 */
		nd = s_malloc(sizeof *nd);
		nd->is_leaf = false;
		nd->ch = (char) 0x7F;
		nd->weight = min[0]->weight + min[1]->weight;
		nd->left = min[0];
		nd->right = min[1];
		nd->left->parent = nd->right->parent = nd;

		queue__push(q2, &nd);
	}
	S_assert(q1->n + q2->n == 1);

	/* TODO: return nd; */
	if (q1->n) {
		fputs("This shouldn't normally happen.\n", stderr);
		queue__pop(q1, &root);
	} else {
		queue__pop(q2, &root);
	}

	queue__cleanup(q1);
	queue__cleanup(q2);
	return root;
}

/*
 * Data representation:
 *
 * [[len1, f1],
 *  [len2, f2],
 *  ...
 *  [lenn, fn]]
 */
int **
huffman_build_coding_table(struct huff_node *node, int **table,
		const unsigned long long path, const short path_len)
{
	int i;

	if (table == NULL) {
		table = s_calloc(1 << CHAR_BIT, sizeof table[0]);

		/* XXX: TODO: explain or fix */
		table[0] = s_calloc(2 * (1 << CHAR_BIT), sizeof **table);
		for (i = 1; i < (1 << CHAR_BIT); i++)
			table[i] = table[i - 1] + 2;
	}

	if (node->is_leaf || node->left == NULL && node->right == NULL) {
		S_assert(node->left == NULL);
		S_assert(node->right == NULL);
		table[node->ch][0] = path_len;
		table[node->ch][1] = path;
	}
	if (node->left) {
		huffman_build_coding_table(node->left, table,
				path << 1, path_len + 1);
	}
	if (node->right) {
		huffman_build_coding_table(node->right, table,
				path << 1 | 1, path_len + 1);
	}

	return table;
}

int
huffman_encoded_msg_len(const unsigned char *msg, const int msg_len,
		int **table)
{
	register int enc_len = 0, i = 0;

	for (; i < msg_len; i++)
		enc_len += table[msg[i]][0];

	return enc_len;
}

unsigned char *
huffman_encode(const unsigned char *msg, const int msg_len,
		int **table)
{
	unsigned char *enc_msg;
	register int i = 0, enc_idx = 0, bits_remaining = CHAR_BIT;

	enc_msg = s_calloc((huffman_encoded_msg_len(msg, msg_len, table) - 1) / 8 + 1,
			sizeof *enc_msg);

	while (i < msg_len) {
		if (bits_remaining - table[msg[i]][0] < 0) {
			/* next code doesn't fit into the current byte */
			/*
			 * example:
			 * enc_msg[enc_idx] = *****000
			 * bits_remaining = 3
			 * table[msg[i]][0] = 5
			 *   enc_msg[enc_idx:enc_idx + 1] = *****___ __000000
			 */
			enc_msg[enc_idx++] |= (table[msg[i]][1] >> (table[msg[i]][0] - bits_remaining)) &
					((1 << (bits_remaining)) - 1);
			bits_remaining -= table[msg[i]][0]; /* less than 0 */
			enc_msg[enc_idx] |= (table[msg[i]][1] << (CHAR_BIT + bits_remaining)) & 0xFF;
			bits_remaining += CHAR_BIT;
		} else if (bits_remaining - table[msg[i]][0] >= 0) {
			/* usual case */
			enc_msg[enc_idx] |= (table[msg[i]][1] << (bits_remaining - table[msg[i]][0])) &
					((1 << (bits_remaining)) - 1);
			bits_remaining -= table[msg[i]][0];

			if (bits_remaining == 0) {
				bits_remaining = CHAR_BIT;
				enc_idx++;
			}
		}
		i++;
	}

	return enc_msg;
}

void
huffman_canonical()
{
}

void
huffman_decode(unsigned char *enc_msg)
{
}

void
huffman_destroy_tree(struct huff_node *node)
{
	if (node->left)
		huffman_destroy_tree(node->left);
	if (node->right)
		huffman_destroy_tree(node->right);
	free(node);
}

int
main(int argc, char **argv)
{
	char *str;
	int len = 0;
	struct huff_node *huffman_tree;
	unsigned int *frequencies;
	int **enc_table;
	unsigned char *encoded_msg;
	int encoded_msg_len;
	int i, nameless;
	char *binary_repr;

	str = s_malloc(100000UL + 2UL);
	scanf("%s", str);
	len = strlen(str);

	/*
	 * Special case: one character
	 */
	nameless = true;
	for (i = 1; i < len; i++) {
		if (str[i - 1] != str[i]) {
			nameless = false;
			break;
		}
	}
	if (nameless) {
		printf("%d\n%c 0\n", len, str[0]);
		for (i = 0; i < (len - 1) / 8; i++)
			fputs("00 ", stdout);
		fputs("00\n", stdout);
		goto exit;
	}

	frequencies = count_frequencies((unsigned char *) str, len);
	huffman_tree = huffman_build_tree(frequencies);
	enc_table = huffman_build_coding_table(huffman_tree, NULL, 0, 0);
	encoded_msg_len = huffman_encoded_msg_len((unsigned char *) str, len, enc_table);
	encoded_msg = huffman_encode((unsigned char *) str, len, enc_table);

	printf("%d\n", encoded_msg_len);

	for (i = 0; i < (1 << CHAR_BIT); i++) {
		if (enc_table[i][0]) {
			/* FFFFFFFFFFUCK YOU, LITTLE-ENDIAN. YOU DON'T MAKE SENSE */
			/*binary_repr = bits_to_str(&enc_table[i][1], enc_table[i][0], 0);*/
			binary_repr = int_to_bitstr(enc_table[i][1]);
			printf("%c %s\n", i, binary_repr +
					(CHAR_BIT * sizeof (int)) - enc_table[i][0]);
			free(binary_repr);
		}
	}
	binary_repr = bytes_to_str(encoded_msg, (encoded_msg_len - 1) / 8 + 1);
	puts(binary_repr);

	free(binary_repr);
	free(frequencies);
	free(encoded_msg);
	free(enc_table[0]);
	free(enc_table);
	huffman_destroy_tree(huffman_tree);

exit:
	free(str);
	return 0;
}
